﻿using System.Diagnostics.CodeAnalysis;
/// <summary>
/// https://leetcode-cn.com/problems/permutations-ii/
/// </summary>
public class Solution
{
    private class IntListComparer : IEqualityComparer<IList<int>>
    {
        public bool Equals(IList<int>? x, IList<int>? y)
        {
            if (x == null)
                return y == null;
            if (y == null)
                return false;
            return x.SequenceEqual(y);
        }

        public int GetHashCode([DisallowNull] IList<int> obj)
        {
            var result = new HashCode();
            foreach (var item in obj)
                result.Add(item);
            return result.ToHashCode();
        }
    }
    private IEnumerable<int> RemoveOne(IEnumerable<int> values, int value)
    {
        bool removed = false;
        foreach (var val in values)
        {
            if (val == value && !removed)
            {
                removed = true;
                continue;
            }
            yield return val;
        }
    }

    private IEnumerable<IEnumerable<int>> Permute(IEnumerable<int> nums, IEnumerable<int> cur)
    {
        if (!nums.Any())
            return new IEnumerable<int>[] { cur };

        var result = new List<IEnumerable<int>>();
        foreach (var num in nums)
            result.AddRange(this.Permute(this.RemoveOne(nums, num), cur.Concat(new int[] { num })));
        return result;
    }

    public IList<IList<int>> PermuteUnique(int[] nums)
    {
        HashSet<IList<int>> result = new HashSet<IList<int>>(new IntListComparer());
        foreach (var p in this.Permute(nums, Array.Empty<int>()))
        {
            var list = new List<int>(p);
            _ = result.Add(list);
        }
        return new List<IList<int>>(result);
    }
}